package DynamicProgramming;

/**
 * @description: 背包问题，复习背包问题、滚动数组
 * @author: w_jingbo
 * @date: 2023/9/6
 * @Copyright: 博客：http://coisini.wang
 */
public class BagProblem {


    public static void main(String[] args) {
        int[] weight = new int[]{1,3,4} ;
        int[] value = new int[]{15,20,30} ;
        int bagWeight = 4 ;

        int[][] dp = new int[weight.length][bagWeight+1] ;



        // 初始化数组
        for(int i = bagWeight ; i >= weight[0] ; i-- ){
            dp[0][i] = dp[0][weight[0]] + value[0] ;
        }

        for(int i = 1 ; i < weight.length ; i++){
            for(int j = 0 ; j <= bagWeight ; j++){
                if(j < weight[i]){
                    dp[i][j] = dp[i-1][j] ;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }
        //打印dp数组，用于理解
        for(int i = 0 ; i < weight.length ; i++){
            for(int j = 0 ; j <= bagWeight ; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println(dp[weight.length-1][bagWeight]);


        System.out.println("=================================================");
        //滚动数组版
        int[] dp1 = new int[bagWeight+1] ;

        for(int i = 0 ; i < weight.length ; i++){
            for(int j = bagWeight ; j >= weight[i] ; j--){
                dp1[j] = Math.max(dp1[j],dp1[j-weight[i]] + value[i]);
                System.out.print(dp1[j] + " ");
            }
            System.out.println();
        }
        System.out.println(dp1[bagWeight]);
    }
}
